#include <iostream>
#include <map>
#include <vector>
using namespace std;

void merge(vector<int>& nums, int l, int r)
{
	if (l == r) return;
	int mid = (l + r) >> 1;
	merge(nums, l, mid);
	merge(nums, mid + 1, r);
	vector<int> temp(r - l + 1);
	int i = l, j = mid + 1, k = 0;
	while (i <= mid && j <= r)
	{
		temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
	}
	while (i <= mid)
	{
		temp[k++] = nums[i++];
	}
	while (j <= r)
	{
		temp[k++] = nums[j++];
	}
	for (int i = l; i <= r; ++i)
	{
		nums[i] = temp[i - l];
	}
}

int main()
{
	srand(time(0));
	vector<int> nums;
	for (int i = 0; i < 1e5; ++i)
		nums.push_back(rand() % 500);
	merge(nums, 0, nums.size() - 1);
	for (auto x : nums)
	{
		cout << x << ' ';
	}
}